Random numbers are required in many applications. An example is the use of random numbers in cryptographic tokens such as chip-cards. Both the symmetric and asymmetric ciphering algorithms require the availability of a high-quality random number source for key generation. Random numbers are also used for generating challenges in authentification protocols, to create padding bytes and blinding values in random masking.
Pseudo-random number generators based on cryptographic secure deterministic algorithms can be employed for creating random numbers for the above purposes. However, a physical source of true randomness is always needed for algorithm seeding. As a result, a cryptographic token must always feature a true random number generator among its peripheral devices. The most important feature of a high-quality random number generator is the unpredictability of the produced bit stream: an observer or attacker must not be able to carry out any useful prediction about the random number generator's output even if its design is known.
True random number generators produce random bit streams from non-deterministic stochastic processes such as electronic noise or radioactive decay. However, only electronic noise sources—such as thermal or shot noise—can be used in an integrated implementation. This is especially true for the use of random number generators in chip-cards, where low chip area and power consumption, as well as high production yield and low design costs are of high importance.
The implementations for generating random streams suitable for integrated environments reported in literature are based on three different techniques: direct amplification of a white noise source, jittered oscillator sampling, and time-discreet chaotic maps. Each type of random source, even if well designed, produces a bit stream that usually shows a certain level of correlation due to bandwidth limitation, fabrication tolerances, aging and temperature drifts, deterministic disturbances, etc. By designing a random number generator which is based on all three techniques, the advantages of each method can be exploited in order to improve the quality of the overall random number source.
A more effective solution for increasing the quality of the ransom bit stream is the post-processing of the raw bit stream from the source with carefully designed correcting and de-correlating algorithms. The post-processing can additionally feature compression so that a lower speed bit stream with increased statistical quality is generated from a high-speed near-random input stream by “distilling” its entropy.
FIG. 1 shows a block diagram of a random number generator based on jittered oscillator sampling as known in the prior art. The random number generator basically consists of two free-running signal sources G1 and G2, and a sample and hold element SH. The output signal S1 of the first signal source G1 has a frequency f1 that is higher than the frequency f2 of the signal S2 output by the second signal source G2. The first signal S1 is used as a data input for the sample and hold element SH while the second signal S2 is used to trigger the sample and hold element. The outputs s[i] of the sample and hold element SH correspond to the values of the first signal S1 at the moments of sampling and are used as random values. The throughput of the random number generator is given by the frequency f2 of the second signal source G2.
The principle of jittered oscillator sampling is further illustrated by means of FIG. 2. Shown are the waveforms of the first signal S1 and the second signal S2 of the first and second oscillator G1 and G2, respectively. The first signal S1 is sampled with every rising edge of the second signal S2. Because of jitter, the period of the second signal S2 varies from cycle to cycle, so that the precise moment of the rising edge also varies with each cycle. The variations can be assumed to follow a Gaussian distribution with a standard deviation τ. As a result of these variations, the first signal S1 is sometimes sampled at a low value “0” and sometimes at a high value “1”. Because of the random distribution of the jitter, the sampled values are also randomly distributed and can be used for generating a random bit stream.
In FIG. 2, only the jitter of the second signal S2 is shown, while in reality, the first signal S1 also jitters. However, for the creation of randomness, only the relative variation of the frequencies between the first and second signals S1 and S2 is of interest, so that for the purpose of illustrating, jitter is assumed to be associated with the second signal S2 only.
For a correct functioning of the random number generator, it is important that the frequency f1 of the first signal S1 is not a integer multiple of the frequency f2 of the second signal S2, as otherwise beating may occur which leads to periodicity in the generated bit stream. Further, periodic disturbances such as the system clock, which can synchronize the second signal source G2 and thus dramatically reduce its jitter, must be minimized.
The entropy of the random values output by the random number generator is due to the jitter of the second signal source, the latter being the only source of randomness in the system. However, the jitter-to-mean-period ratio is usually quite small so that the distribution of the random values is not as uniform as desired. One way to overcome this problem is to increase the frequency f1 of the first signal S1 so that given a standard deviation τ of the jitter of the second signal S2, many periods of signal S1 will occur within a time interval of +/−3τ. However, the frequency f1 of the first signal S1 cannot be increased indefinitely because of limits in implementing high-frequency oscillators. Another way to increase the random stream quality is to increase the jitter-to-mean-period ratio of the second signal S2 by means of an amplified noise source inside the second signal source G2. This approach however, results in an increase in chip area and power required for implementation.